class Solution {
public:
    vector<vector<int>> graph;   
    vector<int> ret,size,dp;   
     
    void dfs1(int u){
        size[u] = 1;
        dp[u] = 0;
        for(int& v : graph[u]){
            if(size[v] == 0){
                dfs1(v);
                
                size[u] += size[v];
                dp[u] += dp[v] + size[v];
            }
        }
    }    
                                        
    void dfs2(int u){
        
        ret[u] = dp[u];
        for(int& v : graph[u]){
            if(ret[v] != 0) continue;
            int x = dp[u];
            int y = size[u];
            
            size[u] -= size[v];
            dp[u] -= dp[v] + size[v];
            size[v] += size[u];
            dp[v] += dp[u] + size[u];
            
            dfs2(v);
            
            size[u] = y;
            dp[u] = x;
            
        }
    }                                    
                                        
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        graph.resize(n);
        ret.resize(n);
        size.resize(n);
        dp.resize(n);
        
        for(auto& vc : edges){
            graph[vc[0]].push_back(vc[1]);
            graph[vc[1]].push_back(vc[0]);
        }
    
        dfs1(0);
        dfs2(0);
        
        return ret;
    }
};
